package java学习.leetcode.editor.cn;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author 刘世锦
 * 2022-10-06 10:30:18	 当前时间
 */
//给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。 
//
// 异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。 
//
// 
//
// 示例 1: 
//
// 
//输入: s = "cbaebabacd", p = "abc"
//输出: [0,6]
//解释:
//起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
//起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。
// 
//
// 示例 2: 
//
// 
//输入: s = "abab", p = "ab"
//输出: [0,1,2]
//解释:
//起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。
//起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。
//起始索引等于 2 的子串是 "ab", 它是 "ab" 的异位词。
// 
//
// 
//
// 提示: 
//
// 
// 1 <= s.length, p.length <= 3 * 104 
// s 和 p 仅包含小写字母 
// 
// Related Topics 哈希表 字符串 滑动窗口 
// 👍 1022 👎 0

public class 找到字符串中所有字母异位词{
	public static void main(String[] args) {
		Solution solution = new 找到字符串中所有字母异位词().new Solution();
//		String s = "cbaebabacd", p = "abc";
		String s = "abab", p = "ab";
		System.out.println(solution.findAnagrams(s, p));
	}
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
//		    0 1 2 3 4 5 6 7 8 9
//输入: s = "c b a e b a b a c d", p = "abc"
//输出: [0,6]
//解释:
//起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
//起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。

	/**
	 * 1. 先记录p的词频
	 * 滑动窗口。
	 * end ,start 记录该区间s的每个字符出现个数。
	 * 与p进行比较，若两数组equals，则加入list
	 *
	 *
	 */
	public List<Integer> findAnagrams(String s, String p) {
		ArrayList<Integer> list = new ArrayList<>();
		int[] map = new int[26];
		for (int i = 0; i < p.length(); i++) {
			map[p.charAt(i)-'a']++;
		}
//		滑动窗口
		int[] sw = new int[26];
		int start = 0,end = 0;
		while (end<s.length()){
//			若end-start<p.length(), 则end→,统计当前s的每个字符个数。
			sw[s.charAt(end)-'a']++;
			if (end-start==p.length()-1){
//				满足后，比较此时 sw 与 p 的字符出现次数是否一致。，一致则加入list
				if (Arrays.equals(sw,map)){
					list.add(start);
				}
//				随后 start→，保持窗口 p.length()的长度
				sw[s.charAt(start)-'a']--;
				start++;
			}
			end++;
		}
		return list;
	}


// 	超时了
		public List<Integer> findAnagrams2(String s, String p) {
		ArrayList<Integer> list = new ArrayList<>();
		int length = p.length();
		char[] charp = p.toCharArray();
		Arrays.sort(charp);
		String ps = Arrays.toString(charp);
//		            0 1 2 3
		//输入: s = "a b a b", p = "ab"
		//输出: [0,1,2]
		for (int i = 0; i < s.length()-length+1; i++) {
			String substring = s.substring(i, i + length);
			char[] chars = substring.toCharArray();
			Arrays.sort(chars);
			String toString = Arrays.toString(chars);
			if (toString.equals(ps)){
				list.add(i);
			}
		}
		return  list;

	}
}
//leetcode submit region end(Prohibit modification and deletion)

}
